/*
 * @lc app=leetcode.cn id=4 lang=golang
 *
 * [4] 寻找两个正序数组的中位数
 */

// @lc code=start

func findMedianSortedArrays(numsA []int, numsB []int) float64 {
	lenA, lenB := len(numsA), len(numsB)
	if lenB > lenA {
		lenA, lenB = lenB, lenA
		numsA, numsB = numsB, numsA
	}
	if lenB == 0 {
		return getMidInArr(numsA)
	}
	// 以下 nums1, nums2 均不为空
	// 如果两个数组长度和不超过5的话, 就直接排序吧
	if lenA+lenB < 5 {
		return orderArr(numsA, numsB)
	}

	iA, fA, iB, fB := lenA/2, lenA%2, lenB/2, lenB%2
	c := iA - iB
	// A比B长
	if fA == 0 { // 中间两个值
		if fB == 0 {
			if numsA[iA] < numsB[iB-1] { // iA-1, iA, iB-1, iB
				return findMedianC(numsA[iA:lenA], numsB[0:iB], c, false)
			} else if numsA[iA-1] > numsB[iB] { // iB-1, iB, iA-1, iA
				return findMedianC(numsA[:iA], numsB[iB:lenB], c, true)
			} else if numsA[iA-1] > numsB[iB-1] {
				if numsA[iA] < numsB[iB] { // hB-1, hA-1, hA, hB
					return float64(numsA[iA-1]+numsA[iA]) / 2
				} else { // hB-1, hA-1, hB, hA
					return findMedianC(numsA[iA-1:lenA], numsB[0:iB+1], c, false)
				}
			} else {
				if numsA[iA] > numsB[iB] { // h1, h2, h2+, h1+
					return float64(numsB[iB-1]+numsB[iB]) / 2
				} else { // hA-1, hB-1, hA, hB
					return findMedianC(numsA[:iA+1], numsB[iB-1:lenB], c, true)
				}
			}
		} else {
			if numsB[iB] < numsA[iA-1] { // iB, iA-1, iA
				return findMedianC(numsA[:iA], numsB[iB:lenB], c, true)
			} else if numsB[iB] < numsA[iA] {
				return float64(numsB[iB])
			} else { // iA-1, iA, iB
				return findMedianC(numsA[iA:lenA], numsB[0:iB+1], c, false)
			}
		}
	} else {
		if fB == 0 {
			if numsA[iA] < numsB[iB-1] { // iA, iB-1, iB
				return findMedianC(numsA[iA:lenA], numsB[0:iB], c, false)
			} else if numsA[iA] < numsB[iB] {
				return float64(numsA[iA])
			} else { // iB-1, iB, iA
				return findMedianC(numsA[:iA+1], numsB[iB:lenB], c, true)
			}
		} else {
			if numsA[iA] == numsB[iB] {
				return float64(numsA[iA])
			}
			if numsA[iA] > numsB[iB] { // iB, iA
				return findMedianC(numsA[:iA+1], numsB[iB:lenB], c, true)
			} else { // iA, iB
				return findMedianC(numsA[iA:lenA], numsB[0:iB+1], c, false)
			}
		}
	}
}

// A: 23456789
// B: 12
func findMedianC(numsA, numsB []int, c int, isLeft bool) float64 {
	var pA, pB int
	var lB = len(numsB)
	var d int
	if c > lB {
		d = lB / 2
	} else {
		d = c / 2
	}
	c -= d
	if isLeft {
		if numsA[d] > numsB[d] {
			pB += d
		} else {
			pA += d
		}
		for i := 0; i < c; i++ {
			if pB < lB && numsA[pA] > numsB[pB] {
				pB++
			} else {
				pA++
			}
		}
		return findMedianSortedArrays(numsA[pA:], numsB[pB:])
	} else {
		pA, pB = len(numsA)-1, lB-1
		if numsA[d] < numsB[d] {
			pB -= d
		} else {
			pA -= d
		}
		for i := 0; i < c; i++ {
			if pB >= 0 && numsA[pA] < numsB[pB] {
				pB--
			} else {
				pA--
			}
		}
		return findMedianSortedArrays(numsA[:pA+1], numsB[:pB+1])
	}
}

// 排序法返回中位数
func orderArr(nums1, nums2 []int) float64 {
	ints := append(nums1, nums2...)
	sort.Ints(ints)
	return getMidInArr(ints)
}

// 返回中位数
func getMidInArr(nums []int) float64 {
	le := len(nums)
	h := le / 2
	if le%2 == 0 {
		return float64(nums[h-1]+nums[h]) / 2
	} else {
		return float64(nums[h])
	}
}

// @lc code=end

